package com.java.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 图
 * 图的简单实现
 *
 * @author 19252
 * @date 2020/8/1
 */
public class Graph {

    /**
     * 存储顶点
     */
    private ArrayList<String> vertexList;

    /**
     * 存储图的邻接矩阵
     */
    private int[][] edges;

    /**
     * 图中边的条数
     */
    private int edgesNum;

    /**
     * 记录图中的顶点是否被遍历
     */
    private boolean[] isVisited;

    public Graph(int n) {
        this.edges = new int[n][n];
        this.vertexList = new ArrayList<>();
        edgesNum = 0;
        isVisited = new boolean[n];
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");
        graph.addVertex("D");
        graph.addVertex("E");
        graph.addVertex("F");

        // 添加边
        // A-B
        graph.insertEdge(0, 1, 1);
        // A-C
        graph.insertEdge(0, 2, 1);
        // B-C
        graph.insertEdge(1, 2, 1);
        // B-D
        graph.insertEdge(1, 3, 1);
        // B-E
        graph.insertEdge(1, 4, 1);
        // D-F
        graph.insertEdge(3, 5, 1);

        graph.showGraph();

        System.out.println("dfs");
        graph.dfs();
        // graph.dfs(5);
        System.out.println();
        System.out.println("bfs");
        graph.bfs();
    }


    public void bfs() {
        bfs(0);
    }

    public void bfs(int index) {
        isVisited = new boolean[vertexList.size()];
        System.out.print(getByIndex(index) + "->");
        Queue<Integer> queue = new LinkedList<>();
        queue.add(index);
        isVisited[index] = true;
        int vertex;
        while (!queue.isEmpty()) {
            vertex = queue.poll();
            for (int i = 0; i < vertexList.size(); i++) {
                int closeVertex = edges[vertex][i];
                if (closeVertex != 0 && !isVisited[i]) {
                    queue.add(i);
                    isVisited[i] = true;
                    System.out.print(getByIndex(i) + "->");
                }
            }
        }
    }

    /**
     * 以默认的顶点开始图的深度优先遍历
     */
    public void dfs() {
        dfs(0);
    }

    /**
     * 以指定的顶点开始图的深度优先遍历
     *
     * @param index 顶点的index
     */
    public void dfs(int index) {
        // 输出被遍历到的点
        System.out.print(getByIndex(index) + "->");
        // 标记已被访问过
        isVisited[index] = true;
        // 寻找没有被访问过的邻接顶点
        int closeVertex;
        while (true) {
            closeVertex = getCloseVertex(index);
            if (closeVertex != -1) {
                dfs(closeVertex);
            } else {
                break;
            }
        }
    }

    public boolean isVisited(int index) {
        return isVisited[index];
    }

    public int getCloseVertex(int index) {
        for (int i = 0; i < edges.length; i++) {
            // 属于与该顶点有连接的点，并且没有访问过
            if (edges[index][i] != 0 && !isVisited(i)) {
                return i;
            }
        }
        return -1;
    }

    public void addVertex(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * @param vertex1 两个有联系的顶点中的一个
     * @param vertex2 两个有有联系的顶点中的另一个
     * @param weight  两个顶点互相连接的边的权值
     */
    public void insertEdge(int vertex1, int vertex2, int weight) {
        edges[vertex1][vertex2] = weight;
        edges[vertex2][vertex1] = weight;
        edgesNum++;
    }

    /**
     * 获取图中的顶点的个数
     *
     * @return 顶点的个数
     */
    public int getVertexNums() {
        return vertexList.size();
    }

    /**
     * 图中边的条数
     *
     * @return 边的条数
     */
    public int getEdgesNums() {
        return edgesNum;
    }

    /**
     * 根据图中顶点的编号返回该顶点的值
     *
     * @param index 索引
     * @return 顶点的值
     */
    public String getByIndex(int index) {
        return vertexList.get(index);
    }

    /**
     * 返回一条边的权值
     *
     * @param vertex1 边的一个顶点
     * @param vertex2 边的另一个顶点
     * @return 边的权值
     */
    public int getWeightOfTwoVertex(int vertex1, int vertex2) {
        return edges[vertex1][vertex2];
    }

    /**
     * 展示图的邻接矩阵
     */
    public void showGraph() {
        for (int[] edge : edges) {
            for (int e : edge) {
                System.out.print(e + " ");
            }
            System.out.println();
        }
    }

    public ArrayList<String> getVertex() {
        return vertexList;
    }

    public void setVertex(ArrayList<String> vertex) {
        this.vertexList = vertex;
    }

    public int[][] getEdges() {
        return edges;
    }

    public void setEdges(int[][] edges) {
        this.edges = edges;
    }

    public int getEdgesNum() {
        return edgesNum;
    }

    public void setEdgesNum(int edgesNum) {
        this.edgesNum = edgesNum;
    }

    public boolean[] getIsVisited() {
        return isVisited;
    }

    public void setIsVisited(boolean[] isVisited) {
        this.isVisited = isVisited;
    }
}
